#pragma once
#include "stdafx.h"

template<typename T> 
class FastArray{
private:
	T * data;
	unsigned int * flags;
	unsigned int * flagsStack;
	unsigned int stackPtr;
	T initialValue;
	unsigned int dataSize;
public:
	FastArray(const T & initVal, unsigned int size);
	inline void isEmpty() { return stackPtr==0; }
	const T & getFrom(unsigned int idx) const;
	void putAt(unsigned int idx, const T & val);
	inline void initWithVal(const T & initVal) { initialValue = initVal; stackPtr = 0; }
	~FastArray();
};

template<typename T>
FastArray<T>::FastArray(const T & initVal, unsigned int size){
	initialValue = initVal;
	data = new T[size];
	flags = new unsigned int [size];
	flagsStack = new unsigned int [size];
	stackPtr = 0;
	dataSize = size;
}

template<typename T>
FastArray<T>::~FastArray() {
	delete data;
	delete flags;
	delete flagsStack;
	stackPtr = 0;
}

template<typename T>
const T & FastArray<T>::getFrom(unsigned int idx) const {
	ASSERT(stackPtr<=dataSize);
	if ((flags[idx] <  stackPtr) && (flagsStack[flags[idx]]==idx)) {
		return data[idx];
	}
	return initialValue;
}

template<typename T>
void FastArray<T>::putAt(unsigned int idx,const T & val) {
	if ((flags[idx] < stackPtr) && (flags[idx]>=0) && (flagsStack[flags[idx]] == idx)) {
		//this is the case when the cell is already initialized
		data[idx] = val;
	} else {
		flags[idx] = stackPtr;
		ASSERT((stackPtr>=0) && (stackPtr<dataSize));
		flagsStack[stackPtr] = idx;
		stackPtr++;
		data[idx] = val;
	}
}
